#include "graph.h"
#include <stdlib.h>
#include <stdio.h>

Graph CreateDirectGraph(void)
{
    int N, i;
    Vertex v, w;
    Graph G;
    PtrToNode p;

    printf("Number of vertexs:");
    scanf("%d",&N);
    G = (struct GraphRecord *)malloc(sizeof(struct GraphRecord));
    G->vertices = (struct VertexRecord *)malloc(sizeof(struct VertexRecord) * (N + 1));
    G->vexnum = N;

    for (i = 1; i <= N; i++)
        G->vertices[i].adjto = NULL;
    printf("Number of edges:");
    scanf("%d",&N);


    for (i = 1; i <= N; i++)
    {
        scanf("%d%d", &v, &w);
        p = ( struct Node *) malloc( sizeof( struct Node ) );
        p->adjvex = w;
        p->next = G->vertices[v].adjto;//p->next = ________________;
        G->vertices[v].adjto = p;//G->vertices[v].adjto = _______________;
    }
    return G;
}

void DestroyGraph(Graph G)
{
    /*free space*/
    return;
}

Vertex FirstAdjVex(Graph G, Vertex v)
{
    if (G->vertices[v].adjto)
        return G->vertices[v].adjto->adjvex;
    else
        return 0;
}

Vertex NextAdjVex(Graph G, Vertex v, Vertex w)
{
    PtrToNode p;

    p = G->vertices[v].adjto;
    while (p->adjvex != w)
        p = p->next;
    if (p->next)
        return p->next->adjvex;
    return 0;
}

int NumOfVex(Graph G)
{
    return G->vexnum;
}


int Topsort( Graph G, int TopNum[] )
{
    Queue Q;
    int V, W, N;
    int  Counter = 0;
    int *Indegree;
    PtrToNode p;

    N = NumOfVex(G);

    Indegree = (int *)malloc(sizeof(int)*(N + 1));
    for (V=1; V<=N; V++)
        Indegree[V] = 0;


    for (V=1; V<=N; V++)
        for (p =G->vertices[V].adjto; p; p = p->next)
            Indegree[p->adjvex]++;//________________;//indegree of vertex

    Q = CreateQueue( N );
    for (V = 1; V <= N; V++)
        if(Indegree[V] == 0)//if ( _______________ )
            Enqueue( V, Q );


    while ( !IsEmpty( Q ) )
    {
        V = Dequeue( Q );

        TopNum[ ++ Counter ] = V; /* assign next */
        /*
        for (W = ______________; W; W = ______________)
            if ( __________________ )
                Enqueue( W, Q );
                //*/
        for (W = FirstAdjVex(G, V); W; W = NextAdjVex(G,V, W))

            if(W &&Indegree[W]-- &&Indegree[W] == 0)//if ( __________________ )

                Enqueue( W, Q );




    }  /* end-while */
    DisposeQueue( Q ); /* free memory */
    if ( Counter != N )
        return 0;
    return 1;
}









